package com.zp.self.module.level_4_算法练习.算法.动态规划;

/**
 * @author By ZengPeng
 */
public class 力扣_300_最长递增子序列 {
    //测试
    public static void main(String[] args) {
//        System.out.println(new 力扣_300_最长递增子序列().search(4,new int[]{1,5,7},2));//4
//        System.out.println(new 力扣_300_最长递增子序列().search(6,new int[]{1,5,7},2));//4
//        System.out.println(new 力扣_300_最长递增子序列().search(8,new int[]{1,5,7},2));//4
//        System.out.println(new 力扣_300_最长递增子序列().search(5,new int[]{1,5,7},2));//4
        System.out.println(new 力扣_300_最长递增子序列().lengthOfLIS(new int[]{10,9,2,5,3,7,101,18}));//4
        System.out.println(new 力扣_300_最长递增子序列().lengthOfLIS(new int[]{0,1,0,3,2,3}));//4
        System.out.println(new 力扣_300_最长递增子序列().lengthOfLIS(new int[]{7,7,7,7,7,7,7}));//1
        System.out.println(new 力扣_300_最长递增子序列().lengthOfLIS(new int[]{7}));//1
    }

    /**
    题目：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
     子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
     例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
      
     示例 1：
     输入：nums = [10,9,2,5,3,7,101,18]
     输出：4
     解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

     示例 2：
     输入：nums = [0,1,0,3,2,3]
     输出：4

     示例 3：
     输入：nums = [7,7,7,7,7,7,7]
     输出：1


    分析：【PR 💜💜💜💜】
       1.动态规划+递归：当我们在遍历过程中，找到下一个值next时：
                    问题就变成了以next为起点，找后面的长度。此时越靠后的数据，就会被多次访问。
                    我们用数组dp[]缓存住这些下标的子序列长度结果
                 递归：我们可以找到以当前节点为起点的最大值，以托于下一个值的计算结果。
                        --执行用时：73 ms, 在所有 Java 提交中击败了5.33%的用户      o_o ....
       2.动态规划+迭代：每到一个新的节点，需要判断与前面节点的大小，如果大于前面的节点，那么当前比较当前dp[i],dp[pro]+1的大小
                迭代：dp[i] 的值代表 nums 以 nums[i]结尾的最长子序列长度。即：前面比i小递减的个数
                        --执行用时：60 ms, 在所有 Java 提交中击败了23.18%的用户    (⊙﹏⊙)
                优化：数组对象的nums.length 属性调用浪费时间，改为变量 int len = nums.length;  提升了5ms  （*＾-＾*） 好起来了
                        --执行用时：55 ms, 在所有 Java 提交中击败了70.95%的用户
       大佬.动态规划+迭代+二分法：每次去dp[i]前面找小于 numbs[i]的最大长度，遍历需要O(n)，所以我们需要优化为二分查找【O(log n)】
                                    如果我们定义tails[k]为:子序列长度为：k+1时，最小的那个值
                                    在遍历计算每个 tails[k]，不断更新长度为 [1,k] 的子序列尾部元素值，始终保持每个尾部元素值最小
                                   （例如 [1,5,3]]， 遍历到元素 5时，长度为 2的子序列尾部元素值为 5；tails= [1,5]
                                    当遍历到元素 3 时，尾部元素值应更新至 3，因为 3 遇到比它大的数字的几率更大）。tails= [1,3]
                                    此时：numb[i]>1 则长度为2
                                          numb[i]=1 则长度为1 tails不变
                                          numb[i]=2 则长度为2 tails改变长度为2的下标值为2， tails= [1,2]
                                          numb[i]>3 则长度为3  tails添加元素
                                    所以：二分查找，找到numb[i]要插入的位置，替换值
                                --执行用时：2 ms, 在所有 Java 提交中击败了99.69%的用户

    边界值 & 注意点：
       1.此时我们要用到回溯法：因为可以跳过（删除）中间的值
     **/
    public int lengthOfLIS(int[] nums) {
        // 3.大佬.动态规划+迭代+二分法：
        int len = nums.length,index=0  ;
        int[] dp = new int[len];
        dp[0]=nums[0];
        for (int i = 1; i < len; i++) {
            int newIndex = search(nums[i], dp, index);
            if (newIndex > index) index = newIndex;
            dp[newIndex] = nums[i];
        }
        return index+1;

        // 2.动态规划+迭代：
        /*int len = nums.length;
        int[] dp = new int[len];
        for (int i = 0; i < len; i++) {
            for (int pro = 0; pro < i; pro++) {
                if(nums[pro]<nums[i])
                    dp[i]=Math.max(dp[pro]+1,dp[i]);
            }
        }
        int max=0;
        for (int i : dp)
            max=Math.max(max,i);
        return max+1;*/
        // 1.动态规划+递归：
      /*  int[] dp = new int[nums.length];
        int max =1;
        for (int i = 0; i < dp.length; i++) {
            dfs(i, nums, dp);//找到以index下标为起点的最长子序列
            max = Math.max(max,dp[i]);//遍历dp每个节点的最长序列，返回最大值 。
        }
        return max;*/
    }
    //找到我应该插入的位置
    private int search(int num, int[] dp, int index) {
        int left =0,right = index;
        while (left<=right){
            int mid = left+(right-left)/2;
            if(num >dp[mid]){
                left = mid+1;
            }else  if(num <dp[mid]){
                right=mid-1;
            }else
                return mid;
        }
        return right+1;
    }

    //递归三部曲：单步操作，终止条件，返回值 {10,9,2,5,3,7,101,18}
    /**
     * Description: 明确这个递归的作用：找到以index下标为起点的最长子序列
     * @param index 起点
     * @param nums 目标数组
     * @param dp 结果缓存数组
     * @return int
     */
    private int dfs(int index, int[] nums, int[] dp) {
        if(dp[index]!=0) return dp[index];
        int max=0;
        for (int i = index+1; i < nums.length; i++) {//这里可以提前结束，不用遍历后面每个值
            if(nums[i]>nums[index])
                max = Math.max(max,dfs(i,nums,dp));//---优化：即使不是最大，也应该要记录其长度嘛
        }
        dp[index]=max+1;
        return dp[index];
    }
}
